A Topic Model for Linked Documents and Update Rules for its Estimation.
The latent topic model plays an important role in the unsupervised learning from a corpus, which provides a probabilistic interpretation of the corpus in terms of the latent topic space. An underpinning assumption which most of the topic models are based on is that the documents are assumed to be independent of each other. However, this assumption does not hold true in reality and the relations among the documents are available in different ways, such as the citation relations among the research papers. To address this limitation, in this paper we present a Bernoulli Process Topic (BPT) model, where the interdependence among the documents is modeled by a random Bernoulli process. In the BPT model a document is modeled as a distribution over topics that is a mixture of the distributions associated with the related documents. Although BPT aims at obtaining a better document modeling by incorporating the relations among the documents, it could also be applied to many applications including detecting the topics from corpora and clustering the documents. We apply the BPT model to several document collections and the experimental comparisons against several state-of-the-art approaches demonstrate the promising performance.
FacetCube a framework of incorporating prior knowledge into non%2Dnegative tensor factorization.

Directed Network Community Detection A Popularity and Productivity Link Model.
In this paper, we consider the problem of community detection in directed networks by using probabilistic models. Most existing probabilistic models for community detection are either symmetric in which incoming links and outgoing links are treated equally or conditional in which only one type (i.e., either incoming or outgoing) of links is modeled. We present a probabilistic model for directed network community detection that aims to model both incoming links and outgoing links simultaneously and differentially. In particular, we introduce latent variables node productivity and node popularity to explicitly capture outgoing links and incoming links, respectively. We demonstrate the generality of the proposed framework by showing that both symmetric models and conditional models for community detection can be derived from the proposed framework as special cases, leading to better understanding of the existing models. We derive efficient EM algorithms for computing the maximum likelihood solutions to the proposed models. Extensive empirical studies verify the effectiveness of the new models as well as the insights obtained from the unified framework.
Unsupervised Learning from Linked Documents.
The latent topic model plays an important role in the unsupervised learning from a corpus, which provides a probabilistic interpretation of the corpus in terms of the latent topic space. An underpinning assumption which most of the topic models are based on is that the documents are assumed to be independent of each other. However, this assumption does not hold true in reality and the relations among the documents are available in different ways, such as the citation relations among the research papers. To address this limitation, in this paper we present a Bernoulli Process Topic (BPT) model, where the interdependence among the documents is modeled by a random Bernoulli process. In the BPT model a document is modeled as a distribution over topics that is a mixture of the distributions associated with the related documents. Although BPT aims at obtaining a better document modeling by incorporating the relations among the documents, it could also be applied to many applications including detecting the topics from corpora and clustering the documents. We apply the BPT model to several document collections and the experimental comparisons against several state-of-the-art approaches demonstrate the promising performance.
Directed Network Community Detection A Popularity and Productivity Link Model.
In this paper, we consider the problem of community detection in directed networks by using probabilistic models. Most existing probabilistic models for community detection are either symmetric in which incoming links and outgoing links are treated equally or conditional in which only one type (i.e., either incoming or outgoing) of links is modeled. We present a probabilistic model for directed network community detection that aims to model both incoming links and outgoing links simultaneously and differentially. In particular, we introduce latent variables node productivity and node popularity to explicitly capture outgoing links and incoming links, respectively. We demonstrate the generality of the proposed framework by showing that both symmetric models and conditional models for community detection can be derived from the proposed framework as special cases, leading to better understanding of the existing models. We derive efficient EM algorithms for computing the maximum likelihood solutions to the proposed models. Extensive empirical studies verify the effectiveness of the new models as well as the insights obtained from the unified framework.
CloudDB One Size Fits All Revived.

SLA%2DAware Profit Optimization in Cloud Services via Resource Scheduling.

Incremental spectral clustering by efficiently updating the eigen%2Dsystem.

Knowledge Discovery from Citation Networks.
Abstract—Knowledge discovery from scientific articles has received increasing attentions recently since huge repositories are made available by the development of the Internet and digital databases. In a corpus of scientific articles such as a digital library, documents are connected by citations and one document plays two different roles in the corpus: document itself and a citation of other documents. In the existing topic models, little effort is made to differentiate these two roles. We believe that the topic distributions of these two roles are different and related in a certain way. In this paper we propose a Bernoulli Process Topic (BPT) model which models the corpus at two levels: document level and citation level. In the BPT model, each document has two different representations in the latent topic space associated with its roles. Moreover, the multilevel hierarchical structure of the citation network is captured by a generative process involving a Bernoulli process. The distribution parameters of the BPT model are estimated by a variational approximation approach. In addition to conducting the experimental evaluations on the document modeling task, we also apply the BPT model to a well known scientific corpus to discover the latent topics. The comparisons against state-ofthe-art methods demonstrate a very promising performance. Keywords-Unsupervised learning; latent models; text mining I.
Combining link and content for community detection a discriminative approach.

Ordering innovators and laggards for product categorization and recommendation.
Different buyers exhibit different purchasing behaviors. Some rush to purchase new products while others tend to be more cautious, waiting for reviews from people they trust. In market analysis, the former group of buyers is often referred to as innovators and early adopters while the latter group is referred to as laggards. The adoption behavior is a dynamic feature of the user and varies over groups of products, e.g., innovators of literature may not be the innovators of electronics. The adoption order of users is a dynamic feature of the product, which can help to predict the future potential buyers. However, such dynamic features are usually unavailable in the description of products. In this paper, we study the user behavior of an online review website— Epinions.com. We first propose to model user adoption behaviors by creating a total ordering among users who rate the products in a given category. We develop a greedy algorithm and a Markov-chain based algorithm for computing the category total ordering. Next, we show that by using user behavior information, we can more accurately predict the category of a new product as well as predict which users will follow. Furthermore, by using the Epinion.com trust network as evidence, we demonstrate that our total ordering can group users into communities that closely resemble the trust network. Thus the adoption order can be a useful feature in recommendation systems.
A Bayesian Approach Toward Finding Communities and Their Evolutions in Dynamic Social Networks.

A latent topic model for linked documents.

Association Rule Mining on Streams.
Let I = {i1,  ·  ·  · , im} be a set of items. Let S be a stream of transactions in a sequential order, where each transaction is a subset of I. For an itemset X, which is a subset of I, a transaction T in S is said to contain the itemset X if X ⊆ T. The support of X is defined as the fraction of transactions in S that contain X. For a given support threshold s, X is frequent if the support of X is greater than or equal to s%, i.e., if at least s % transactions in S contain X. For a given confidence threshold c, an association rule X ⇒ Y holds if X ∪ Y is frequent and at least c % of transactions in S that contain X also contain Y. The problem of association rule mining on streams is to discover all association rules that hold in a stream of transactions. HISTORICAL BACKGROUND In 1993, Rakesh Agrawal et al. [1] proposed the framework for association rule mining. Since this seminal work, a lot of researches have been done to improve the efficiency of association rule mining algorithms, to extend the definition of associations rule, and to apply association rule mining to
Analyzing communities and their evolutions in dynamic social networks.

On evolutionary spectral clustering.
Evolutionary clustering is an emerging research area essential to important applications such as clustering dynamic Web and blog contents and clustering data streams. In evolutionary clustering, a good clustering result should fit the current data well, while simultaneously not deviate too dramatically from the recent history. To fulfill this dual purpose, a measure of temporal smoothness is integrated in the overall measure of clustering quality. In this article, we propose two frameworks that incorporate temporal smoothness in evolutionary spectral clustering. For both frameworks, we start with intuitions gained from the well-known k-means clustering problem, and then propose and solve corresponding cost functions for the evolutionary spectral clustering problems. Our solutions to the evolutionary spectral clustering problems provide more stable and consistent clustering results that are less sensitive to short-term noises while at the same time are adaptive to longterm cluster drifts. Furthermore, we demonstrate that our methods provide the optimal solutions to the relaxed versions of the corresponding evolutionary k-means clustering problems. Performance experiments over a number of real and synthetic data sets illustrate our evolutionary spectral clustering methods provide more robust clustering results that are not sensitive to noise and can adapt to data drifts.
Integrating clustering and multi%2Ddocument summarization to improve document understanding.
Document understanding techniques such as document clustering and multi-document summarization have been receiving much attention in recent years. Current document clustering methods usually represent documents as a term-document matrix and perform clustering algorithms on it. Although these clustering methods can group the documents satisfactorily, it is still hard for people to capture the meanings of the documents since there is no satisfactory interpretation for each document cluster. In this paper, we propose a new language model to simultaneously cluster and summarize the documents. By utilizing the mutual influence of the document clustering and summarization, our method makes (1) a better document clustering method with more meaningful interpretation and (2) a better document summarization method taking the document context information into consideration.
Probabilistic polyadic factorization and its application to personalized recommendation.
Multiple-dimensional, i.e., polyadic, data exist in many applications, such as personalized recommendation and multipledimensional data summarization. Analyzing all the dimensions of polyadic data in a principled way is a challenging research problem. Most existing methods separately analyze the marginal relationships among pairwise dimensions and then combine the results afterwards. Motivated by the fact that various dimensions of polyadic data jointly affect each other, we propose a probabilistic polyadic factorization approach to directly model all the dimensions simultaneously in a unified framework. We then show the connection between the probabilistic polyadic factorization and a non-negative version of the Tucker tensor factorization. We provide detailed theoretical analysis of the new modeling framework, discuss implementation techniques for our models, and propose several extensions to the basic framework. We then apply the proposed models to the application of personalized recommendation. Extensive experiments on a social bookmarking dataset, Delicious, and a paper citation dataset, CiteSeer, demonstrate the effectiveness of the proposed models.
Efficient computation of personal aggregate queries on blogs.
There is an exploding amount of user-generated content on the Web due to the emergence of “Web 2.0 ” services, such as Blogger, MySpace, Flickr, and del.icio.us. The participation of a large number of users in sharing their opinion on the Web has inspired researchers to build an effective “information filter ” by aggregating these independent opinions. However, given the diverse groups of users on the Web nowadays, the global aggregation of the information may not be of much interest to different groups of users. In this paper, we explore the possibility of computing personalized aggregation over the opinions expressed on the Web based on a user’s indication of trust over the information sources. The hope is that by employing such “personalized ” aggregation, we can make the recommendation more likely to be interesting to the users. We address the challenging scalability issues by proposing an efficient method, that utilizes two core techniques: Non-Negative Matrix Factorization and Threshold Algorithm, to compute personalized aggregations when there are potentially millions of users and millions of sources within a system. We show that, through experiments on real-life dataset, our personalized aggregation approach indeed makes a significant difference in the items that are recommended and it reduces the query computational cost significantly, often more than 75%, while the result of personalized aggregation is kept accurate enough.
Facetnet a framework for analyzing communities and their evolutions in dynamic networks.
We discover communities from social network data, and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over time, due to changes to individuals’ roles and social status in the network as well as changes to individuals ’ research interests. We present an innovative algorithm that deviates from the traditional two-step approach to analyze community evolutions. In the traditional approach, communities are first detected for each time slice, and then compared to determine correspondences. We argue that this approach is inappropriate in applications with noisy data. In this paper, we propose FacetNet for analyzing communities and their evolutions through a robust unified
Detecting splogs via temporal dynamics using self%2Dsimilarity analysis.
This article addresses the problem of spam blog (splog) detection using temporal and structural regularity of content, post time and links. Splogs are undesirable blogs meant to attract search engine traffic, used solely for promoting affiliate sites. Blogs represent popular online media, and splogs not only degrade the quality of search engine results, but also waste network resources. The splog detection problem is made difficult due to the lack of stable content descriptors. We have developed a new technique for detecting splogs, based on the observation that a blog is a dynamic, growing sequence of entries (or posts) rather than a collection of individual pages. In our approach, splogs are recognized by their temporal characteristics and content. There are three key ideas in our splog detection framework. (a) We represent the blog temporal dynamics using selfsimilarity matrices defined on the histogram intersection similarity measure of the time, content, and link attributes of posts, to investigate the temporal changes of the post sequence. (b) We study the blog temporal characteristics using a visual representation derived from the self-similarity measures. The visual signature reveals correlation between attributes and posts, depending on the type of blogs (normal blogs and splogs). (c) We propose two types of novel temporal features to capture the splog temporal characteristics. In our splog detector, these novel features are combined
Splog Detection Using Self%2Dsimilarity Analysis on Blog Temporal Dynamics.
This paper focuses on spam blog (splog) detection. Blogs are highly popular, new media social communication mechanisms. The presence of splogs degrades blog search results as well as wastes network resources. In our approach we exploit unique blog temporal dynamics to detect splogs. There are three key ideas in our splog detection framework. We first represent the blog temporal dynamics using self-similarity matrices defined on the histogram intersection similarity measure of the time, content, and link attributes of posts. Second, we show via a novel visualization that the blog temporal characteristics reveal attribute correlation, depending on type of the blog (normal blogs and splogs). Third, we propose the use of temporal structural properties computed from self-similarity matrices across different attributes. In a splog detector, these novel features are combined with content based features. We extract a content based feature vector from different parts of the blog – URLs, post content, etc. The dimensionality of the feature vector is reduced by Fisher linear discriminant analysis. We have tested an SVM based splog detector using proposed features on real world datasets, with excellent results (90 % accuracy).
Identifying opinion leaders in the blogosphere.
Opinion leaders are those who bring in new information, ideas, and opinions, then disseminate them down to the masses, and thus influence the opinions and decisions of others by a fashion of word of mouth. Opinion leaders capture the most representative opinions in the social network, and consequently are important for understanding the massive and complex blogosphere. In this paper, we propose a novel algorithm called InfluenceRank to identify opinion leaders in the blogosphere. The InfluenceRank algorithm ranks blogs according to not only how important they are as compared to other blogs, but also how novel the information they can contribute to the network. Experimental results indicate that our proposed algorithm is effective in identifying influential opinion leaders.
Identifying opinion leaders in the blogosphere.
Opinion leaders are those who bring in new information, ideas, and opinions, then disseminate them down to the masses, and thus influence the opinions and decisions of others by a fashion of word of mouth. Opinion leaders capture the most representative opinions in the social network, and consequently are important for understanding the massive and complex blogosphere. In this paper, we propose a novel algorithm called InfluenceRank to identify opinion leaders in the blogosphere. The InfluenceRank algorithm ranks blogs according to not only how important they are as compared to other blogs, but also how novel the information they can contribute to the network. Experimental results indicate that our proposed algorithm is effective in identifying influential opinion leaders.
Splog Detection using Content%2C Time and Link Structures.
This paper focuses on spam blog (splog) detection. Blogs are highly popular, new media social communication mechanisms and splogs corrupt blog search results as well as waste network resources. In our approach we exploit unique blog temporal dynamics to detect splogs. The key idea is that splogs exhibit high temporal regularity in content and post time, as well as consistent linking patterns. Temporal content regularity is detected using a novel autocorrelation of post content. Temporal structural regularity is determined using the entropy of the post time difference distribution, while the link regularity is computed using a HITS based hub score measure. Experiments based on the annotated ground truth on real world dataset show excellent results on splog detection tasks with 90 % accuracy. 1
Evolutionary spectral clustering by incorporating temporal smoothness.

Structural and temporal analysis of the blogosphere through community factorization.
The blogosphere has unique structural and temporal properties since blogs are typically used as communication media among human individuals. In this paper, we propose a novel technique that captures the structure and temporal dynamics of blog communities. In our framework, a community is a set of blogs that communicate with each other triggered by some events (such as a news article). The community is represented by its structure and temporal dynamics: a community graph indicates how often one blog communicates with another, and a community intensity indicates the activity level of the community that varies over time. Our method, community factorization, extracts such communities from the blogosphere, where the communication among blogs is observed as a set of subgraphs (i.e., threads of discussion). This community extraction is formulated as a factorization problem in the framework of constrained optimization, in which the objective is to best explain the observed interactions in the blogosphere over time. We further provide a scalable algorithm for computing solutions to the constrained optimization problems. Extensive experimental studies on both synthetic and real blog data demonstrate that our technique is able to discover meaningful communities that are not detectable by traditional methods.
Incremental Spectral Clustering With Application to Monitoring of Evolving Blog Communities.
In recent years, spectral clustering method has gained attentions because of its superior performance compared to other traditional clustering algorithms such as K-means algorithm. The existing spectral clustering algorithms are all off-line algorithms, i.e., they can not incrementally update the clustering result given a small change of the data set. However, the capability of incrementally updating is essential to some applications such as real time monitoring of the evolving communities of websphere or blogsphere. Unlike traditional stream data, these applications require incremental algorithms to handle not only insertion/deletion of data points but also similarity changes between existing items. This paper extends the standard spectral clustering to such evolving data by introducing the incidence vector/matrix to represent two kinds of dynamics in the same framework and by incrementally updating the eigenvalue system. Our incremental algorithm, initialized by a standard spectral clustering, continuously and efficiently updates the eigenvalue system and generates instant cluster labels, as the data set is evolving. The algorithm is applied to a blog data set. Compared with recomputation of the solution by standard spectral clustering, it achieves similar accuracy but with much lower computational cost. Close inspection into the blog content shows that the incremental approach can discover not only the stable blog communities but also the evolution of the individual multi-topic blogs.


Capturing User Interests by Both Exploitation and Exploration.

Information flow modeling based on diffusion rate for prediction and ranking.
We address the problem of ranking question answerers according to their credibility, characterized here by the probability that a given question answerer (user) will be awarded a best answer on a question given the answerer’s question-answering history. This probability (represented by θ) is considered to be a hidden variable that can only be estimated statistically from specific observations associated with the user, namely the number b of best answers awarded, associated with the number n of questions answered. The more specific problem addressed is the potentially high degree of uncertainty associated with such credibility estimates when they are based on small numbers of answers. We address this problem by a kind of Bayesian smoothing. The credibility estimate will consist of a mixture of the overall population statistics and those of the specific user. The greater the number of questions asked, the greater will be the contribution of the specific user statistics relative to those of the overall population. We use the Predictive Stochastic Complexity (PSC) as an accuracy measure to evaluate several methods that can be used for the estimation. We compare our technique (Bayesian Smoothing (BS)) with maximum a priori (MAP) estimation, maximum likelihood (ML) estimation and Laplace smoothing. 1
Eigen%2Dtrend trend analysis in the blogosphere based on singular value decompositions.
The blogosphere---the totality of blog-related Web sites--- has become a great source of trend analysis in areas such as product survey, customer relationship, and marketing. Existing approaches are based on simple counts, such as the number of entries or the number of links. In this paper, we introduce a novel concept, coined eigen-trend, to represent the temporal trend in a group of blogs with common interests and propose two new techniques for extracting eigentrends in blogs. First, we propose a trend analysis technique based on the singular value decomposition. Extracted eigentrends provide new insights into multiple trends on the same keyword. Second, we propose another trend analysis technique based on a higher-order singular value decomposition. This analyzes the blogosphere as a dynamic graph structure and extracts eigen-trends that reflect the structural changes of the blogosphere over time. Experimental studies based on synthetic data sets and a real blog data set show that our new techniques can reveal a lot of interesting trend information and insights in the blogosphere that are not obtainable from traditional count-based methods.
Blog Community Discovery and Evolution Based on Mutual Awareness Expansion.
There are information needs involving costly decisions that cannot be efficiently satisfied through conventional web search engines. Alternately, community centric search can provide multiple viewpoints to facilitate decision making. We propose to discover and model the temporal dynamics of thematic communities based on mutual awareness, where the awareness arises due to observable blogger actions and the expansion of mutual awareness leads to community formation. Given a query, we construct a directed action graph that is time-dependent, and weighted with respect to the query. We model the process of mutual awareness expansion using a random walk process and extract communities based on the model. We propose an interaction space based representation to quantify community dynamics. Each community is represented as a vector in the interaction space and its evolution is determined by a novel interaction correlation method. We have conducted experiments with a real-world blog dataset and have promising results for detection as well as insightful results for community evolution. 1.
Eigen%2Dtrend trend analysis in the blogosphere based on singular value decompositions.
The blogosphere---the totality of blog-related Web sites--- has become a great source of trend analysis in areas such as product survey, customer relationship, and marketing. Existing approaches are based on simple counts, such as the number of entries or the number of links. In this paper, we introduce a novel concept, coined eigen-trend, to represent the temporal trend in a group of blogs with common interests and propose two new techniques for extracting eigentrends in blogs. First, we propose a trend analysis technique based on the singular value decomposition. Extracted eigentrends provide new insights into multiple trends on the same keyword. Second, we propose another trend analysis technique based on a higher-order singular value decomposition. This analyzes the blogosphere as a dynamic graph structure and extracts eigen-trends that reflect the structural changes of the blogosphere over time. Experimental studies based on synthetic data sets and a real blog data set show that our new techniques can reveal a lot of interesting trend information and insights in the blogosphere that are not obtainable from traditional count-based methods.
The Splog Detection Task and A Solution Based on Temporal and Link Properties.
Spam blogs (splogs) have become a major problem in the increasingly popular blogosphere. Splogs are detrimental in that they corrupt the quality of information retrieved and they waste tremendous network and storage resources. We study several research issues in splog detection. First, in comparison to web spam and email spam, we identify some unique characteristics of splog. Second, we propose a new online task that captures the unique characteristics of splog, in addition to tasks based on the traditional IR evaluation framework. The new task introduces a novel time-sensitive detection evaluation to indicate how quickly a detector can identify splogs. Third, we propose a splog detection algorithm that combines traditional content features with temporal and link regularity features that are unique to blogs. Finally, we develop an annotation tool to generate ground truth on a sampled subset of the TREC-Blog dataset. We conducted experiments on both offline (traditional splog detection) and our proposed online splog detection task. Experiments based on the annotated ground truth set show excellent results on both offline and online splog detection tasks. 1.
Catch the moment maintaining closed frequent itemsets over a data stream sliding window.
This paper considers the problem of mining closed frequent itemsets over a data stream  sliding window using limited memory space. We design a synopsis data structure to monitor  transactions in the sliding window so that we can output the current closed frequent  itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot  monitor all possible itemsets. However, monitoring only frequent itemsets will make it  impossible to detect new itemsets when they become frequent. In this paper, we introduce  a compact data structure, the closed enumeration tree (CET), to maintain a dynamically  selected set of itemsets over a sliding window. The selected itemsets contain a boundary  between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data  stream are reflected by boundary movements in the CET. In other words, a status change  of any itemset (e.g., from non-frequent to frequent) must occur through the boundary.
Loadstar A Load Shedding Scheme for Classifying Data Streams.
We consider the problem of resource allocation in mining multiple data streams. Due to the large volume and the high speed of streaming data, mining algorithms must cope with the e#ects of system overload. How to realize maximum mining benefits under resource constraints becomes a challenging task. In this paper, we propose a load shedding scheme for classifying multiple data streams. We focus on the following problems: i) how to classify data that are dropped by the load shedding scheme? and ii) how to decide when to drop data from a stream? We introduce a quality of decision (QoD) metric to measure the level of uncertainty in classification when exact feature values of the data are not available because of load shedding. A Markov model is used to predict the distribution of feature values and we make classification decisions using the predicted values and the QoD metric. Thus, resources are allocated among multiple data streams to maximize the quality of classification decisions. Furthermore, our load shedding scheme is able to learn and adapt to changing data characteristics in the data streams. Experiments on both synthetic data and real-life data show that our load shedding scheme is e#ective in improving the overall accuracy of classification under resource constraints. keywords: data mining, data streams, load shedding, classification, quality of decision, feature prediction, Markov model.
Loadstar Load Shedding in Data Stream Mining.
In this demo, we show that intelligent load shedding is essential in achieving optimum results in mining data streams under various resource constraints. The Loadstar system introduces load shedding techniques to classifying multiple data streams of large volume and high speed. Loadstar uses a novel metric known as the quality of decision (QoD) to measure the level of uncertainty in classification. Resources are then allocated to sources where uncertainty is high. To make optimum classification decisions and accurate QoD measurement, Loadstar relies on feature prediction to model the data dropped by the load shedding mechanism. Furthermore, Loadstar is able to adapt to the changing data characteristics in data streams. The system thus offers a nice solution to data mining with resource constraints. 1
Frequent Subtree Mining %2D An Overview.
Mining frequent subtrees from databases of labeled trees is a new research field that has  many practical applications in areas such as computer networks, Web mining, bioinformatics, XML  document mining, etc. These applications share a requirement for the more expressive power of labeled  trees to capture the complex relations among data entities. Although frequent subtree mining is  a more difficult task than frequent itemset mining, most existing frequent subtree mining algorithms  borrow techniques from the relatively mature association rule mining area. This paper provides an  overview of a broad range of tree mining algorithms. We focus on the common theoretical foundations  of the current frequent subtree mining algorithms and their relationship with their counterparts  in frequent itemset mining. When comparing the algorithms, we categorize them according to their  problem definitions and the techniques employed for solving various subtasks of the subtree mining  problem. In addition, we also present a thorough performance study for a representative family of  algorithms.
Correction to %22Mining Closed and Maximal Frequent Subtrees from Databases of Labeled Rooted Trees%22.
Abstract—Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. One important problem in mining databases of trees is to find frequently occurring subtrees. Because of the combinatorial explosion, the number of frequent subtrees usually grows exponentially with the size of frequent subtrees and, therefore, mining all frequent subtrees becomes infeasible for large tree sizes. In this paper, we present CMTreeMiner, a computationally efficient algorithm that discovers only closed and maximal frequent subtrees in a database of labeled rooted trees, where the rooted trees can be either ordered or unordered. The algorithm mines both closed and maximal frequent subtrees by traversing an enumeration tree that systematically enumerates all frequent subtrees. Several techniques are proposed to prune the branches of the enumeration tree that do not correspond to closed or maximal frequent subtrees. Heuristic techniques are used to arrange the order of computation so that relatively expensive computation is avoided as much as possible. We study the performance of our algorithm through extensive experiments, using both synthetic data and data sets from real applications. The experimental results show that our algorithm is very efficient in reducing the search space and quickly discovers all closed and maximal frequent subtrees. Index Terms—Trees, graph algorithms, data mining, mining methods and algorithms, frequent subtree, closed frequent subtree, maximal frequent subtree.
Mining Closed and Maximal Frequent Subtrees from Databases of Labeled Rooted Trees.
Abstract—Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. One important problem in mining databases of trees is to find frequently occurring subtrees. Because of the combinatorial explosion, the number of frequent subtrees usually grows exponentially with the size of frequent subtrees and, therefore, mining all frequent subtrees becomes infeasible for large tree sizes. In this paper, we present CMTreeMiner, a computationally efficient algorithm that discovers only closed and maximal frequent subtrees in a database of labeled rooted trees, where the rooted trees can be either ordered or unordered. The algorithm mines both closed and maximal frequent subtrees by traversing an enumeration tree that systematically enumerates all frequent subtrees. Several techniques are proposed to prune the branches of the enumeration tree that do not correspond to closed or maximal frequent subtrees. Heuristic techniques are used to arrange the order of computation so that relatively expensive computation is avoided as much as possible. We study the performance of our algorithm through extensive experiments, using both synthetic data and data sets from real applications. The experimental results show that our algorithm is very efficient in reducing the search space and quickly discovers all closed and maximal frequent subtrees. Index Terms—Trees, graph algorithms, data mining, mining methods and algorithms, frequent subtree, closed frequent subtree, maximal frequent subtree.
Canonical forms for labelled trees and their applications in frequent subtree mining.
Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. In this paper, we first present two canonical forms for labeled rooted unordered trees--the breadth-first canonical form (BFCF) and the depth-first canonical form (DFCF). Then the canonical forms are applied to the frequent subtree mining problem. Based on the BFCF, we develop a vertical mining algorithm, RootedTreeMiner, to discover all frequently occurring subtrees in a database of labeled rooted unordered trees. The RootedTreeMiner algorithm uses an enumeration tree to enumerate all (frequent) labeled rooted unordered subtrees. Next, we extend the definition of the DFCF to labeled free trees and present an Apriori-like algorithm, FreeTreeMiner, to discover all frequently occurring subtrees in a database of labeled free trees. Finally, we study the performance and the scalability of our algorithms through extensive experiments based on both synthetic data and datasets from real applications.
Mining association rules with non%2Duniform privacy concerns.
Privacy concerns have become an important issue in data mining. A popular way to preserve privacy is to randomize the dataset to be mined in a systematic way and mine the randomized dataset instead. On the other hand, people usually have different privacy concerns for different attributes in data. E.g., in survey data, the sensitivity of questions varies. Appropriate use of this information can lead to more accurate data mining results. However, this information has not been fully utilized by many privacy preserving association rule mining algorithms. In this paper, we generalize the privacy preserving association rule mining problem by allowing different attributes to have different levels of privacy, that is, using different randomization factors for values of different attributes in the randomization process. We also propose an efficient algorithm RE (Recursive Estimation) to estimate the support of itemsets under this framework. Both theoretical and empirical results show that the use of non-uniform randomization factors improves the accuracy of the support estimates, compared to the use of one conservative randomization factor.
Moment Maintaining Closed Frequent Itemsets over a Stream Sliding Window.
This paper considers the problem of mining closed frequent itemsets over a sliding window using limited memory space. We design a synopsis data structure to monitor transactions in the sliding window so that we can output the current closed frequent itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot monitor all possible itemsets. However, monitoring only frequent itemsets will make it impossible to detect new itemsets when they become frequent. In this paper, we introduce a compact data structure, the closed enumeration tree (CET), to maintain a dynamically selected set of itemsets over a sliding-window. The selected itemsets consist of a boundary between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data stream are reflected by boundary movements in the CET. In other words, a status change of any itemset (e.g., from non-frequent to frequent) must occur through the boundary. Because the boundary is relatively stable, the cost of mining closed frequent itemsets over a sliding window is dramatically reduced to that of mining transactions that can possibly cause boundary movements in the CET. Our experiments show that our algorithm performs much better than previous approaches.
CMTreeMiner Mining Both Closed and Maximal Frequent Subtrees.
Tree structures are used extensively in domains such as computational  biology, pattern recognition, XML databases, computer networks,  and so on. One important problem in mining databases of trees is  to find frequently occurring subtrees. However, because of the combinatorial  explosion, the number of frequent subtrees usually grows exponentially  with the size of the subtrees. In this paper, we present CMTreeMiner,  a computationally e#cient algorithm that discovers all closed and  maximal frequent subtrees in a database of rooted unordered trees. The  algorithm mines both closed and maximal frequent subtrees by traversing  an enumeration tree that systematically enumerates all subtrees, while  using an enumeration DAG to prune the branches of the enumeration tree  that do not correspond to closed or maximal frequent subtrees. The enumeration  tree and the enumeration DAG are defined based on a canonical  form for rooted unordered trees--the depth-first canonical form (DFCF).
HybridTreeMiner An Efficient Algorithm for Mining Frequent Rooted Trees and Free Trees Using Canonical Form.
Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. In this paper, we present HybridTreeMiner, a computationally efficient algorithm that discovers all frequently occurring subtrees in a database of rooted unordered trees. The algorithm mines frequent subtrees by traversing an enumeration tree that systematically enumerates all subtrees. The enumeration tree is defined based on a novel canonical form for rooted unordered trees -- the breadth-first canonical form (BFCF). By extending the definitions of our canonical form and enumeration tree to free trees, our algorithm can efficiently handle databases of free trees as well. We study the performance of our algorithms through extensive experiments based on both synthetic data and datasets from real applications. The experiments show that our algorithm is competitive in comparison to known rooted tree mining algorithms and is faster by one to two orders of magnitudes compared to a known algorithm for mining frequent free trees.
Indexing and Mining Free Trees.
Tree structures are used extensively in domains such as computational biology, pattern recognition,  computer networks, and so on. In this paper, we present an indexing technique for free  trees and apply this indexing technique to the problem of mining frequent subtrees. We first  define a novel representation, the canonical form, for rooted trees and extend the definition to  free trees. We also introduce another concept, the canonical string, as a simpler representation  for free trees in their canonical forms. We then apply our tree indexing technique to the frequent  subtree mining problem and present FreeTreeMiner, a computationally e#cient algorithm that  discovers all frequently occurring subtrees in a database of free trees. Our mining algorithm  is a variation of the traditional a priori method for mining frequent itemsets. We study the  performance and the scalability of our algorithms through extensive experiments based on both  synthetic data and datasets from two real applications: a dataset of chemical compounds and a  dataset of Internet multicast trees. The experiments show that our algorithm scales linearly in  the cardinality of the database.
